package main.Q1801_1900;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Q1801_1810 {
    public static void main(String[] args) {
        System.out.println("Question1801：");
        System.out.println("Question1802：有界数组中指定下标处的最大值");
        System.out.println("Question1803：");
        System.out.println("Question1804：");
        System.out.println("Question1805：");
        System.out.println("Question1806：");
        System.out.println("Question1807：替换字符串中的括号内容");
        System.out.println("Question1808：");
        System.out.println("Question1809：");
        System.out.println("Question1810：");
    }
}

class Question1802 {
    public int maxValue(int n, int index, int maxSum) {
        long l = 0, r = maxSum;
        maxSum -= n;//因为数组中所有的数均为正整数，所以减去n，剩余的表示可以填的数
        while (l < r) {
            long m = l + r + 1 >> 1;//m表示index指向位置的高度
            long count = m * m;//计算当index的位置高度为m时，数组所有元素的和
            if (m > index) count -= (m - index - 1) * (m - index) / 2;//如果左边越界，就减去左边多的
            if (m > (n - index)) count -= (m - (n - index - 1) - 1) * (m - (n - index - 1)) / 2;//如果右边越界，就减去右边多的
            if (count > maxSum) r = m - 1;//二分法判断
            else l = m;
        }
        return (int) l + 1;
    }
}

class Question1807 {
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> map = new HashMap<>();
        for (List<String> list : knowledge) {
            map.put(list.get(0), list.get(1));
        }
        StringBuffer result = new StringBuffer();
        for (int i = 0; i < s.length(); ) {
            if (s.charAt(i) == '(') {
                StringBuffer temp = new StringBuffer();
                i++;
                while (s.charAt(i) != ')') {
                    temp.append(s.charAt(i));
                    i++;
                }
                if (map.containsKey(temp.toString())) {
                    result.append(map.get(temp.toString()));
                } else {
                    result.append("?");
                }
            } else {
                result.append(s.charAt(i));
            }
            i++;
        }
        return result.toString();
    }
}